// 问题代码。见FlowUS解析

// 防止内存不足：terminate called after throwing an instance of 'std::bad_alloc'
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int a[100001];
int sum[100001][21];
using ll = long long;

// 存储拆分 和为m的所有方案。total为方案的数量
vector<int> Fangan[200];
int total = 0;
int temp[20];

int n, m, q;

// 凑m的方案
void dfs(int dep, int pre, int s) { // dep:深度,pre:上一个数, s 和
  if (s == m) {                     // 如果和等于m，输出 s % m == 0
    total++;
    for (int i = 1; i <= dep - 1; i++) {
      int k = temp[i];
      Fangan[total].push_back(k);
    }
    return;
  }
  for (int i = pre + 1; i < m; i++) { // 从上一个数的值开始循环
    temp[dep] = i;                    // 保存次深度的数
    dfs(dep + 1, i, s + i); // 递归：深度+1，上一个数：i，和+i;
  }
}
// 查询[L,R]  区间
int query(int L, int R) {
  int res = 0;
  for (int i = 1; i <= total; i++) {
    int t = 1;
    for (auto x : Fangan[i]) {
      int w = sum[R][x] - sum[L - 1][x];
      // cout << ":" << sum[R][x] << " " << sum[L - 1][x] << endl;
      (t *= w) %= MOD;
    }
    (res += t) %= MOD;
  }
  return res;
}

ll ppower(ll x, ll p) {
  ll ans = 1;
  while (p != 0) {
    if (p % 2 == 1)
      ans = (ans * x) % MOD;
    x = (x * x) % MOD;
    p = p >> 1;
  }
  return ans;
}

/*  test
 若m是3,则生成所有和为3的方案
 0 1 2
 1 2*/
void test() {
  // cout << "total:" << total << endl;
  for (int i = 1; i <= total; i++) {
    for (auto x : Fangan[i]) {
      cout << x << " ";
    }
    cout << endl;
  }
}

int main() {
  cin >> n >> m >> q;
  dfs(1, -1, 0);
  test();

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] %= m;
  }
  for (int i = 1; i <= n; i++) {
    for (int k = 0; k < m; k++) {
      sum[i][k] = sum[i - 1][k];
    }
    int k = a[i];
    sum[i][k] += 1;
  }

  for (int i = 1; i <= q; i++) {
    int L, R;
    cin >> L >> R;
    int ans = query(L, R);
    int k = sum[R][0] - sum[L - 1][0];

    // cout << ans << ";" << int(pow(2, k)) << endl;
    // 注意0的情况， Cn0+Cn1+Cn2+...+Cnn=2^n
    cout << (ans + ppower(2, k)) % MOD << endl;
  }
  return 0;
}